package 栈和队列;

import common.TreeNode;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;

/**
 * ---------------------------------------------------------
 * <h></h>
 * <p>
 * 给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
 *
 * 二叉树的根是数组 nums 中的最大元素。
 * 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
 * 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
 * 返回有给定数组 nums 构建的 最大二叉树 。
 *
 *  
 *
 * 示例 1：
 *          -6-
 *    3-           -5
 *       2-     0
 *          1
 *
 * 输入：nums = [3,2,1,6,0,5]
 * 输出：[6,3,5,null,2,0,null,null,1]
 * 解释：递归调用如下所示：
 * - [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
 * - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
 * - 空数组，无子节点。
 * - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
 * - 空数组，无子节点。
 * - 只有一个元素，所以子节点是一个值为 1 的节点。
 * - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
 * - 只有一个元素，所以子节点是一个值为 0 的节点。
 * - 空数组，无子节点。
 *
 * 输入：nums = [3,2,1]
 * 输出：[3,null,2,null,1]
 *
 * 链接：https://leetcode-cn.com/problems/maximum-binary-tree
 * </p>
 * Created by Frank on 2021/4/1.
 * <a href="mailto:frankyao10110@gmail.com">Contact me</a>
 * ---------------------------------------------------------
 */
public class _最大二叉树 {

    public static void main(String[] args) {
        int[] nums = new int[]{3,2,1,6,0,5};
        int[] maxIndexes = parentIndexes(nums);
        System.out.println("maxIndexes: " + Arrays.toString(maxIndexes));
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null || nums.length == 0) return null;

        return findMaxNode(nums, 0, nums.length);
    }

    private static TreeNode findMaxNode(int[] nums, int l, int r) {
        if (l == r) return null;
        //左子树为[l ,maxIdx)，右子树为[maxIdx, r)
        int maxIdx = l;
        for (int i = l + 1; i < r; i++) {
            if (nums[i] >= nums[maxIdx]) maxIdx = i;
        }

        TreeNode root = new TreeNode(nums[maxIdx]);
        root.left = findMaxNode(nums, l, maxIdx);
        root.right = findMaxNode(nums, maxIdx + 1, r);

        return root;
    }

    /**
     * [3,2,1,6,0,5] -> [3(6),0(3),1(2),-1,5(5),3(6)]
     * @return 返回节点的父节点所在下标，如果是根节点，返回-1
     */
    private static int[] parentIndexes(int[] nums) {
        //最大二叉树的父节点，其实就在左边第一个比节点大的或者右边第一个比节点大的之中，左右中比较小的那个就是父节点
        int[] ans = new int[nums.length];
        int[] lis = new int[nums.length];//存放左边第一个比较大的值
        int[] ris = new int[nums.length];//存放右边第一个比较大的值

        //使用单调栈找出第一个比较大的值
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < nums.length; i++) {
            lis[i] = -1;
            ris[i] = -1;
        }

        for (int i = 0; i < nums.length; i++) {
            //[(2,1), (1,2), (0,3)]
            //将要push(3,6), (3,6) > (2,1)，此时(2,1)出栈
            //stack.pop => l = stack.peek(), r[pop] = i
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
               int pop = stack.pop();
               ris[pop] = i;
            }
            if (!stack.isEmpty()) {//每次进来如果不为空，那左边第一个比nums[i]大的就是nums[stack.peek()]
                lis[i] = stack.peek();
            }
            stack.push(i);
        }

        for (int j = 0; j < ans.length; j++) {
            if (lis[j] == -1 && ris[j] == -1) {
                ans[j] = -1;
                continue;
            }

            if (ris[j] == -1){
                ans[j] = lis[j];
            }else if (lis[j] == -1){
                ans[j] = ris[j];
            }else if (nums[lis[j]] < nums[ris[j]]){
               ans[j] = lis[j];
            }else {
                ans[j] = ris[j];
            }
        }

        return ans;
    }

}
